package com.more.offer.algorithm.leetcode.lcode155;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author pinoc
 * @date 2021/8/15
 * @description
 * 按照上面的思路，我们只需要设计一个数据结构，
 * 使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。
 * 因此我们可以使用一个辅助栈，与元素栈同步插入与删除
 */
class MinStack {

	Deque<Integer> xStack;
	Deque<Integer> minStack;

	public MinStack() {
		xStack = new LinkedList<Integer>();
		minStack = new LinkedList<Integer>();
		minStack.push(Integer.MAX_VALUE);
	}

	public void push(int x) {
		xStack.push(x);
		minStack.push(Math.min(minStack.peek(), x));
	}

	public void pop() {
		xStack.pop();
		minStack.pop();
	}

	public int top() {
		return xStack.peek();
	}

	public int getMin() {
		return minStack.peek();
	}
}